package dynamicprogramming.目标和;

import common.ArrayUtil;

/**
 * 给你一个非负整数数组 nums 和一个整数 target 。
 *  向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
 *  例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
 *  返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
 *  示例 1：
 * 输入：nums = [1,1,1,1,1], target = 3
 * 输出：5
 * 解释：一共有 5 种方法让最终目标和为 3 。
 * - 1 + 1 + 1 + 1 + 1 = 3
 * 1 - 1 + 1 + 1 + 1 = 3
 * 1 + 1 - 1 + 1 + 1 = 3
 * 1 + 1 + 1 - 1 + 1 = 3
 * 1 + 1 + 1 + 1 - 1 = 3
 *  示例 2：
 * 输入：nums = [1], target = 1
 * 输出：1
 *  提示：
 *  1 <= nums.length <= 20
 *  0 <= nums[i] <= 1000
 *  0 <= sum(nums[i]) <= 1000
 *  -1000 <= target <= 1000
 *  Related Topics 数组 动态规划 回溯 👍 1965 👎 0
 */
public class Solution {
    public static void main(String[] args) {
        System.out.println(findTargetSumWays(new int[]{1,1,1,1,1},3));
    }

    /**
     * 设d[i][j]表示使用前i个进行运算能得到j的运算方法数量。则动态转移方程为：d[i][j] = d[i-1][j-nums[i]] + d[i-1][j+nums[i]]
     * 注意： j这个值可以是负数，所以二维数组
     * 初始化：第一行需要满足
     * @param nums
     * @param target
     * @return
     */
    public static int findTargetSumWays(int[] nums, int target) {
        int len = nums.length;
        int dp[][] = new int[len][target+1];
        dp[0][0] = 2 ;
        if (nums[0]<target){
            dp[0][nums[0]] = 1;
        }
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < target + 1; j++) {
                dp[i][j] = dp[i-1][j-nums[i]] + dp[i-1][j+nums[i]];
            }
        }
        ArrayUtil.doubleDimensionalArrayPrint(dp);
        return dp[len][target+1] ;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

